1. Field of the Invention
Embodiments of the present invention generally relate to Internet Protocol (IP) network engineering applications, such as network survivability analysis, traffic engineering, and capacity planning. More specifically, the present invention relates to a method and apparatus for finding critical traffic matrices.
2. Description of the Related Art
At present, large operational Internet Protocol (IP) networks are typically made up of hundreds of routers, thousands of links, tens of thousands of routes, and may carry over one peta-byte (=1015 bytes) of traffic per day. The ability to effectively design, engineer, and manage such large networks is crucial to end-to-end network performance and reliability. Until recently, a major obstacle to developing effective methods for network engineering in operational IP networks has been the inability of network operators to measure traffic matrices. A traffic matrix represents the amount of traffic between an origin and a destination in a given network. Similarly, it is an essential input for a variety of IP network engineering applications, such as capacity planning, traffic engineering, and network survivability analysis. Due to the extreme importance of traffic matrices, there have been tremendous efforts and many recent advances in the area of traffic matrix estimation. These techniques have enabled Internet service providers (ISPs) to accurately measure the traffic matrix of their network in a continuous fashion (in the granularity of minutes to an hour).
However, network operators and engineers are now facing the new challenge of having to deal with hundreds or even thousands of traffic matrices, all from real measurement at different time instances. Ideally, network engineers would like to base their design and analysis on all traffic matrices for a significant period of time (e.g., a couple of months). In practice, however, it is usually inconvenient or infeasible to use a large number of traffic matrices. It is inconvenient since many traffic analysis tasks require human intervention (e.g., examine the scenario where congestion has occurred). Dealing with a large number of traffic matrices is very undesirable. It is infeasible since many traffic engineering applications are very computationally expensive. Unfortunately, the solutions developed so far are often quite ad hoc. One common practice is to generate a “peak-all-elements” traffic matrix that has the peak demand for each origin-destination flow. Another approach is to take the traffic, matrix at the network-wide busiest time (i.e., the traffic matrix with the largest total volume). However, none of them are satisfactory. Namely, the “peak-all-elements” traffic matrix is usually too conservative since it significantly over-estimates the total traffic volume, whereas the busiest-time traffic matrix runs the risk of under-estimating the demands since not all flows peak at the network peak.
Thus, it is highly desirable to be able to find a small number of “critical” traffic matrices.